#ifndef __CONTAINER_UTIL_H__
#define __CONTAINER_UTIL_H__

#include <vector>
#include "container_common.h"

using namespace std;


template<class T> 
void fillSequence(T* data, const unsigned long n, T start) {
	for(unsigned long i = 0; i < n; i++) {
		data[i] = start + i;
	}
}

template<class KeyType, class ValueType>
void counting_sort(KeyType* key, ValueType* value, 
			const unsigned long n) {
	/*1. get the min and max value*/
	KeyType min, max;
	min = key[0];
	max = key[0];
	for(unsigned long i = 0; i < n; i++) {
		if(key[i] > max) {
			max = key[i];
		} else if(key[i] < min) {
			min = key[i];
		}
	}

	/*2. scatter the value*/
	const long nBucket = max - min + 1;
	vector<ValueType>* bucket = new vector<ValueType>[nBucket];
	for(unsigned long i = 0; i < n; i++) {
		bucket[key[i] - min].push_back(value[i]);
	}

	/*3. collect the key-value*/
	typename vector<ValueType>::iterator it;
	unsigned long offset = 0;
	for(long bucketId = 0; bucketId < nBucket; bucketId++) {
		if(bucket[bucketId].size() > 0) {
			it = bucket[bucketId].begin();
			for(; it < bucket[bucketId].end(); it++) {
				key[offset] = min + bucketId;
				value[offset] = *it;

				++offset;
			}
		}
	}

	/*4. memory cleanup*/
	delete[] bucket;
}

template<class DataType, class PosType>
void gather(DataType* output, DataType* input, PosType* pos, 
		const unsigned long n) {
	for(unsigned long i = 0; i < n; i++) {
		output[i] = input[pos[i]];
	}
}


/**
 * instead of using the vector, scan twice
 * */
template<class KeyType, class ValueType>
void counting_sort2(KeyType* &key, ValueType* &value, 
			const unsigned long n) {
	/*1. get the min and max value*/
	KeyType min, max;
	min = key[0];
	max = key[0];
	for(unsigned long i = 0; i < n; i++) {
		if(key[i] > max) {
			max = key[i];
		} else if(key[i] < min) {
			min = key[i];
		}
	}
	const long nBucket = max - min + 1;

	/*2. calculate the offset, set count to all zeros*/
	if(nBucket > UINT_MAX) {
		printf("!!!ERROR: nBucket > UINT_MAX");
		exit(-1);
	}
	unsigned int* count = new unsigned int[nBucket];
	unsigned int* offset = new unsigned int[nBucket];
	memset(count, 0, sizeof(unsigned int)*nBucket);
	for(unsigned long i = 0; i < n; i++) {
		count[key[i] - min] += 1;
	}
	offset[0] = 0;
	for(unsigned long i = 1; i < nBucket; i++) {
		offset[i] = offset[i - 1] + count[i - 1];
	}
	memset(count, 0, sizeof(unsigned int)*nBucket);

	/*3. now we gather the results*/
	KeyType* keyOut = new KeyType[n];
	ValueType* valueOut = new ValueType[n];
	unsigned int outIdx = 0;
	for(unsigned long i = 0; i < n; i++) {
		outIdx = offset[key[i] - min] + count[key[i] - min];
		keyOut[outIdx] = key[i];
		valueOut[outIdx] = value[i];
		count[key[i] - min] += 1;
	}

	/*4. return the result back*/
	//memcpy(key, keyOut, sizeof(KeyType)*n);
	//memcpy(value, valueOut, sizeof(ValueType)*n);
	swap(key, keyOut);
	swap(value, valueOut);	

	/*memory cleanup*/
	delete[] count;
	delete[] offset;
	delete[] keyOut;
	delete[] valueOut;
}
#endif /*__CONTAINER_UTIL_H__*/
